module hash_table_module

    implicit none

    type key_value_type
        integer :: key, value
    end type key_value_type

    type hash_table_type
        type(key_value_type), allocatable :: buckets(:)  !! 哈希桶
    contains
        procedure :: allocate, finalize, set_value, get_value, hashing
    end type hash_table_type

contains

    subroutine allocate (self, n)
        class(hash_table_type), intent(out) :: self
        integer, intent(in) :: n

        allocate (self%buckets(n))

    end subroutine allocate

    subroutine finalize(self)
        class(hash_table_type), intent(inout) :: self

        if (allocated(self%buckets)) deallocate (self%buckets)

    end subroutine finalize

    pure integer function hashing(self, key)
        class(hash_table_type), intent(in) :: self
        integer, intent(in) :: key

        hashing = modulo(key, size(self%buckets))

    end function hashing

    !> @note 应该考虑到哈希碰撞
    subroutine set_value(self, key, value)
        class(hash_table_type), intent(inout) :: self
        integer, intent(in) :: key, value

        self%buckets(self%hashing(key)) = key_value_type(key, value)

    end subroutine set_value

    !> @note 应该考虑到哈希碰撞，使用哈希桶索引后，应该遍历哈希桶中的所有元素，得到键对应的正确的值
    pure integer function get_value(self, key)
        class(hash_table_type), intent(in) :: self
        integer, intent(in) :: key

        get_value = self%buckets(self%hashing(key))%value

    end function get_value

end module hash_table_module

program hash_table

    use hash_table_module, only: hash_table_type
    implicit none
    type(hash_table_type) :: tbl

    call tbl%allocate(5)
    call tbl%set_value(27, 10)  ! key = 27, value = 10
    print *, tbl%get_value(27)

end program hash_table
!> 10